package com.lbc.sort;

import java.util.Arrays;

public class RadixSort {
    //  基数排序：800w个数据都能在1s内排完（这个代码目前只能只能排正整数数组）
    //  8000w个数据大约要3.3个G的内存，会内存溢出
    public static void main(String[] args) {
        int [] arr = {53,3,542,748,14,214};
        radixSort(arr);
    }

    // 基数排序方法
    public static void radixSort (int [] arr) {
        // 1.得到数组中最大数的个数
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        //  得到最大数是几位数
        int maxLength = (max + "").length();

        //  定义一个二维数组，表示10个桶，每个桶就是一个一维数组
        //  为了防止数据溢出，每一个桶的大小定义为 arr.length
        //  空间换时间的经典算法
        int [][] bucket = new int[10][arr.length];
        //  定义一个一维数组，记录每一个桶中实际的存放数
        int [] bucketElementCounts = new int [10];

        //  这里我们使用循环进行处理
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            for(int j = 0; j < arr.length; j++) {
                //  得到每个元素对应位的值
                int digitOfElement = arr[j] / n % 10;
                // 放入到对应的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }
            // 按照这个桶的顺序，将桶中的数据取出放入到原来的数组中
            int index = 0;
            for (int k = 0; k < bucketElementCounts.length; k++) {
                // 桶中有数据才将其放入到原数组中
                if (bucketElementCounts[k] != 0) {
                    // 循环该桶（第k个桶），放入
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        // 取出元素放入arr
                        arr[index] = bucket[k][l];
                        index++;
                    }
                }
                // 每一轮过后，都要将每个 bucketElementCounts[k] 置为 0
                bucketElementCounts[k] = 0;
            }
            System.out.println("第"+ (i+1) +"轮，对个位进行排序后 arr = " + Arrays.toString(arr));
        }



    }
}
